package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/19.<br><br>
 *
 * 困难：K 个一组翻转链表
 */
public class Topic25 {
    public static void main(String[] args) {
        Topic25 instance = new Topic25();

        int[] array = new int[] {1,2,3,4,5};
        ListNode head = Util.createList(array);
        Util.printList(instance.reverseKGroup(head, 2));

        array = new int[] {1,2,3,4,5};
        head = Util.createList(array);
        Util.printList(instance.reverseKGroup(head, 1));

        array = new int[] {1};
        head = Util.createList(array);
        Util.printList(instance.reverseKGroup(head, 1));
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int counter = 0;

        while (curr != null && counter < k) {
            curr = curr.next;
            counter++;
        }

        if(counter == k) {
            curr = reverseKGroup(curr, k);

            while (counter-- > 0) {
                ListNode temp = head.next;
                head.next = curr;
                curr = head;
                head = temp;
            }

            head = curr;
        }

        return head;
    }

    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode start = new ListNode(0);
        ListNode pre = start;
        start.next = head;

        ListNode subHead = head;
        while (subHead != null) {
            int count = 0;
            while (subHead != null && count < k) {
                subHead = subHead.next;
                count++;
            }

            if(count == k) {
                ListNode temp = pre.next;
                pre.next = helper(pre.next, subHead);
                temp.next = subHead;

                pre = temp;
            }
        }

        return start.next;
    }

    private ListNode helper(ListNode begin, ListNode end) {
        if(begin == null || begin == end) {
            return begin;
        }

        ListNode start = new ListNode(0);

        while (begin != end) {
            ListNode temp = begin.next;
            begin.next = start.next;
            start.next = begin;

            begin = temp;
        }

        return start.next;
    }
}
